package leetcode.part2;

import org.junit.Test;

public class S392 {
    public boolean isSubsequence(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();
        int[][] dp = new int[sLen+1][tLen+1];
        for (int i = 0; i < sLen; i++) {
            for (int j = 0; j < tLen; j++) {
                int dpi=i+1;
                int dpj=j+1;
                if (s.charAt(i) == t.charAt(j)){
                    dp[dpi][dpj]=dp[dpi-1][dpj-1]+1;
                }else {
                    dp[dpi][dpj]=dp[dpi][dpj-1];
                }
            }
        }
        return dp[sLen][tLen] == s.length();
    }

    @Test
    public void test() {
        String s = "abc", t = "ahbgdc";
        String s1 = "axc", t1 = "ahbgdc";
        String s2 = "aaaaaa", t2 = "bbaaaa";
        System.out.println(isSubsequence(s, t));
        System.out.println(isSubsequence(s1, t1));
        System.out.println(isSubsequence(s2, t2));
    }
}
